home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / fmultimap < prev    next >
Text File  |  1996-04-09  |  7KB  |  221 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- fmultimap.sa: Map from K -> FLIST{T}
  3. -- Author: Benedict A. Gomes <gomes@tiramisu.ICSI.Berkeley.EDU>
  4. -- Copyright (C) 1995, International Computer Science Institute
  5. -- $Id: fmultimap.sa,v 1.4 1996/04/09 10:04:58 borisv Exp $
  6. --
  7. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  8. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  9. -- LICENSE contained in the file: Sather/Doc/License of the
  10. -- Sather distribution. The license is also available from ICSI,
  11. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  12. -------------------------------------------------------------------
  13. class FMULTIMAP{KTP,ETP} < $STR is
  14.    -- A mapping from elements of type K to lists of elements of type T
  15.    -- Unlike FMAP, this class is NOT meant to be used when void
  16.    -- and must be created initially.
  17.    -- 
  18.    -- Implementation: Most of the primitive FMAP routines have been
  19.    -- made private and renamed with a multi_ prefix.  We do permit one
  20.    -- operation that violates the interface, danger_multi_get which
  21.    -- returns the actual flist associated with a particular key (not a
  22.    -- copy of the flist).  This list must *not* be modified and may
  23.    -- well become invalid when other operations are performed upon the
  24.    -- multi-map
  25.    
  26.    private include FMAP{KTP,FLIST{ETP}} 
  27.      target!-> private multi_target!, -- Called in filter
  28.      pair!-> private multi_pair!, -- Called in double, halve, str
  29.      pairs!->private pairs!,
  30.      targets!->private targets!, 
  31.      keys!->private keys!, -- Obsolete
  32.      insert->private multi_insert, -- Called by insert_pair
  33.      insert_pair->private multi_insert_pair,
  34.      create->private old_create,
  35.      delete->private multi_delete,
  36.      filter_not!->, filter!->,
  37.    -- Unchanged private: key_eq, elt_nil,key_nil, is_key_nil, test
  38.    -- get_pair, delete
  39.    -- Publicly included
  40.      copy->copy,
  41.      get-> danger_multi_get,    -- Public, but DANGEROUS.
  42.      is_empty->is_empty,
  43.      has_ind->has_ind,
  44.      clear->clear,
  45.      ind!->ind!,
  46.      n_inds->n_inds,
  47.      str->;
  48.      
  49.    
  50.    private const initially_provide_for: INT := 1;
  51.    
  52.    private attr total_n_targets: INT;
  53.  
  54.    --              ------ Initialization/Duplication ------
  55.    create: SAME is
  56.       -- Create must be called before use
  57.       res ::= old_create(2);
  58.       res.total_n_targets := 0;
  59.       return res;
  60.    end;
  61.    
  62.    copy: SAME is
  63.       res ::= old_create(size);
  64.       res.total_n_targets := 0;
  65.       loop res := res.insert_pair(pair!) end;
  66.       res.hsize := hsize;
  67.       return res;
  68.    end;
  69.    
  70. --              ------ Insertion/Removal --------------- 
  71.    insert(k: KTP, t: ETP): SAME is
  72.       -- Insert a new element "t" associated with "k"
  73.       l: FLIST{ETP}; 
  74.       if has_ind(k) then l := danger_multi_get(k);  else l := #; end;
  75.       l := l.push(t);
  76.       total_n_targets := total_n_targets+1;
  77.       return multi_insert(k,l);     
  78.    end;
  79.    
  80.    insert_pair(p: TUP{KTP,ETP}): SAME is   return insert(p.t1,p.t2);  end;
  81.    
  82.    delete(k: KTP, t: ETP): SAME is
  83.       -- Delete an element "t" from the  elements associated with k
  84.       -- Do nothing if the target does not exist for "k"
  85.       l: FLIST{ETP};  
  86.       if has_ind(k) then l := danger_multi_get(k);  else l := #; end;
  87.       if ~l.has(t) then
  88.      -- Do nothing if the target does not exist
  89.      return self
  90.       end;
  91.       l.delete_elt(t);
  92.       total_n_targets := total_n_targets-1;
  93.       if l.size = 0 then
  94.      return multi_delete(k);
  95.       else
  96.      return multi_insert(k,l);
  97.       end;
  98.    end;
  99.  
  100.    delete_all(k: KTP): SAME is
  101.       -- Delete all elements associated with element "k"
  102.       if has_ind(k) then return multi_delete(k); end;
  103.    end;
  104.       
  105.    --              ------ Access/Measurement --------------
  106.    get_all(k: KTP): FLIST{ETP} is
  107.       -- Return a copy of internal list associated with element "k"
  108.       if has_ind(k) then return danger_multi_get(k).copy;  
  109.       else return #FLIST{ETP} end;
  110.    end;
  111.  
  112.    n_targets: INT is return total_n_targets end;
  113.    -- Return the total number of targets
  114.    
  115.    n_targets(k: KTP): INT is
  116.       -- Return the number of targets for the key "k"
  117.       if has_ind(k) then return danger_multi_get(k).size   else return 0 end;
  118.    end;
  119.  
  120.    size: INT is return n_targets end;
  121.    -- Alias for n_targets to satisfy "CONTAINER{KTP}"
  122.    
  123.     --              ------ Queries/Comparison --------------
  124.    equals(b: $RO_MULTIMAP{KTP,ETP}): BOOL is
  125.       -- Returns true if all of "e"'s elements are equal to self's elts
  126.       -- Ordering is an issue. Should be redefined to be more
  127.       -- precise for particular descendants
  128.       if n_inds /= b.n_inds then return false end;
  129.       if size /= b.size then return false end;
  130.       loop e ::= ind!; 
  131.      if n_targets(e) /= b.n_targets(e) then return false end; 
  132.       end;
  133.       return true ;
  134.    end;
  135.  
  136.    has_pair(k:KTP,t:ETP): BOOL  is
  137.       if has_ind(k) then return danger_multi_get(k).has(t) 
  138.       else return false end;
  139.    end;
  140.  
  141. --              ------ Cursor --------------------------
  142.    pair!: TUP{KTP, ETP} is
  143.       -- Yields pairs of keys and elements - keys may repeat
  144.       loop p: TUP{KTP,FLIST{ETP}} := multi_pair!;
  145.      loop 
  146.         yield #TUP{KTP,ETP}(p.t1,p.t2.elt!);
  147.      end;
  148.       end;
  149.    end;
  150.  
  151.    elt!: ETP is loop yield target!; end; end;
  152.    
  153.    target!: ETP is
  154.       -- Return all the targets in the current multi-map
  155.       loop t: FLIST{ETP} := multi_target!;
  156.      loop yield t.elt! end;
  157.       end;
  158.    end;
  159.    
  160.    target!(once k: KTP): ETP is
  161.       -- Return the elements associated with k
  162.       l: FLIST{ETP};  if has_ind(k) then l := danger_multi_get(k);  
  163.       else l := #; end;
  164.       loop yield l.elt! end;
  165.    end;
  166.  
  167. --              ------ Conversion ----------------------
  168.     str: STR is
  169.       -- Prints out a string version of the array of the components 
  170.       -- that are under $STR, and their associated indices
  171.       res ::= #FSTR("{");
  172.       loop  
  173.      p ::= pair!;
  174.      key ::= p.t1; elt ::= p.t2;
  175.      res := res+",".separate!("["+ind_str(key)+"]="+elt_str(elt));  
  176.       end;
  177.       res := res +"}";
  178.       return(res.str);
  179.    end;
  180.  
  181. --              ------  Private Implementation ---------------
  182.    private ind_str(i: KTP): STR is
  183.       typecase i
  184.       when $STR then return i.str  else return "Unprintable Index" end;
  185.    end;
  186.  
  187.    private elt_str(e: ETP): STR is
  188.       typecase e 
  189.       when $STR then return e.str  else return "Unprintable Element" end;
  190.    end;
  191.    
  192.    private multi_insert_pair(p:TUP{KTP,FLIST{ETP}}):SAME is
  193.       return multi_insert(p.t1,p.t2) 
  194.    end;
  195.    
  196.    private halve_size:SAME 
  197.    -- A new table of half the size of self with self's entries
  198.    -- copied over. 
  199.       pre ~void(self) and hsize<(asize-1)/4 is
  200.       ns::=(asize-1)/2+1; r::=allocate(ns); 
  201.       loop r:=r.multi_insert_pair(multi_pair!) end; 
  202.       r.total_n_targets := total_n_targets;
  203.       SYS::destroy(self);   -- The old one should never be used now.
  204.       return r
  205.    end;
  206.  
  207.    private double_size:SAME 
  208.    -- A new table of twice the size of self with self's entries
  209.    -- copied over. 
  210.       pre ~void(self) is
  211.       ns::=(asize-1)*2+1; r::=allocate(ns); 
  212.       loop r:=r.multi_insert_pair(multi_pair!) end; 
  213.       r.total_n_targets := total_n_targets;
  214.       SYS::destroy(self);   -- The old one should never be used now.
  215.       return r
  216.    end;
  217.  
  218.       
  219. end; -- class FMULTIMAP{KTP,ETP}
  220. -------------------------------------------------------------------
  221.